package stackqueue;

import org.junit.jupiter.api.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 使用队列结构实现栈结构
 */
public class QueueToStack {

    @Test
    public void queueToStack() {
        MyQueueToStack queueToStack = new MyQueueToStack();
        queueToStack.add(1);
        queueToStack.add(2);
        queueToStack.add(3);
        queueToStack.add(4);
        queueToStack.add(5);

        System.out.println(queueToStack.pop());
        System.out.println(queueToStack.pop());
        System.out.println(queueToStack.pop());
        System.out.println(queueToStack.pop());
        System.out.println(queueToStack.pop());
    }

    /**
     * 自定义栈结构
     * 思想：使用两个队列实现，第一个队列用来存储原始数据，第二个队列用来存储第一个队列除了最后一个进来的那个数据的其他的数据，
     * 此时，第一个队列就剩余了一个数据，也就是最后进来的那个数据，
     */
    static class MyQueueToStack extends Stack<Integer> {

        // 第一个队列用来存储原始数据
        Queue<Integer> queue1 = new LinkedList<>();
        // 第二个队列用来存储第一个队列除了最后一个进来的那个数据的其他的数据
        Queue<Integer> queue2 = new LinkedList<>();

        @Override
        public boolean add(Integer data) {
            return queue1.add(data);
        }

        @Override
        public Integer pop() {
            // 将第一个队列中除了最后进来的那个数据之外，其他的数据都备份到第二个队列中
            while (queue1.size() > 1) {
                queue2.add(queue1.poll());
            }
            // 此时，第一个队列就剩余了一个数据，也就是最后进来的那个数据，
            Integer data = queue1.poll();
            // 第一个队列弹出数据后，将剩余的数据还原
            queue1.addAll(queue2);
            queue2.clear();
            return data;
        }
    }

}
